package com.leetcode;

import java.util.ArrayDeque;
import java.util.HashMap;

public class MinimumDepthBinaryTree {
	public int minDepth2(TreeNode root) {
        if (root == null) return 0;
        ArrayDeque<TreeNode> queue = new ArrayDeque<TreeNode>();
        HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
        map.put(root, 1);
        queue.add(root);
        while (!queue.isEmpty()) {
        	TreeNode node = queue.remove();
        	int level = map.get(node);
        	if (node.left == null && node.right == null) return level;
        	if (node.left != null) {
        		queue.add(node.left);
        		map.put(node.left, level+1);
        	}
        	if (node.right != null) {
        		queue.add(node.right);
        		map.put(node.right, level+1);
        	}
        }
        return 0;
    }
	
	public int minDepth(TreeNode root) {
		if (root == null) return 0;
		if (root.left == null) return minDepth(root.right) + 1;
		if (root.right == null) return minDepth(root.left) + 1;
		return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
	}
	
	private class TreeNode {
		TreeNode left;
		TreeNode right;
		int val;
		public TreeNode(int val) {
			this.val = val;
		}
	}
}
